package leetcode.problems;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * _0417 Subsets
 * 子集
 * Created by gmwang on 2018/3/23
 */
public class _0418Subsets {
    /**
     * Given a set of distinct integers, nums, return all possible subsets (the power set).
         Note: The solution set must not contain duplicate subsets.
         Example:
         Input: nums = [1,2,3]
     Output:
        [
             [3],
             [1],
             [2],
             [1,2,3],
             [1,3],
             [2,3],
             [1,2],
             []
         ]
         给出一组不同的整数，数组，返回所有可能的子集。
         注意：解决方案集不能包含重复的子集。
     */

    /**
     * 参考leetcode的大神思路：
     *   起始subset集为：[]
         添加S0后为：[], [S0]
         添加S1后为：[], [S0], [S1], [S0, S1]
         添加S2后为：[], [S0], [S1], [S0, S1], [S2], [S0, S2], [S1, S2], [S0, S1, S2]
         红色subset为每次新增的。显然规律为添加Si后，新增的subset为克隆现有的所有subset，并在它们后面都加上Si。.
     * @param S
     * @return
     */
    public static List<List<Integer>> subsets(int[] S) {
        List<List<Integer>> res = new ArrayList<>();
        res.add(new ArrayList<>());
        Arrays.sort(S);
        for(int i : S) {
            List<List<Integer>> tmp = new ArrayList<>();
            for(List<Integer> sub : res) {
                List<Integer> a = new ArrayList<>(sub);
                a.add(i);
                tmp.add(a);
            }
            res.addAll(tmp);
        }
        return res;
    }
    public static void main(String[] args) {
        int[] nums = {1,2,3,4};
        System.out.println(subsets(nums));
    }
}
